#include<vector>
#include<unordered_set>
#include<algorithm>
using namespace std;
class Solution {
private:

    bool canPartitionKSubsetsCore(vector<int>& nums, vector<int>& groups, int index,int k, int avg) {
        if (index < 0) return true;
        for (int i = 0; i < groups.size(); ++i) {
            if (groups[i] == avg) continue;
            if (groups[i] + nums[index] <= avg) {
                groups[i] += nums[index];
                if (canPartitionKSubsetsCore(nums, groups, index - 1, k, avg))
                    return true;
                groups[i] -= nums[index];
            }
        }
        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for (auto tmp : nums)
            sum += tmp;
        if (sum % k != 0) return false;
        int per = sum / k;
        int len = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > per) return false;
            if (nums[i] == per) {
                ++len;
                --k;
            }
        }
        sort(nums.begin(), nums.end());
        vector<int>groups(k, 0);
        return canPartitionKSubsetsCore(nums, groups, nums.size() - len - 1, k, per);
    }
};

//int main() {
//    vector<int> nums = { 4, 5, 3, 2, 5, 5, 5, 1, 5, 3, 5, 5, 2 };
//    Solution sol;
//    sol.canPartitionKSubsets(nums, 10);
//}